/*
 * @ Created with Clion
 * @ Author Morbid
 * @ Date 2022/07/28
 * @ Time 10:32
 */

#include <cstdlib>

/*!
 * 定义队列链式存储（带头结点）
 * 实现链式存储队列基本操作
 */

typedef int ElemType;

typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode;

typedef struct {
    LinkNode *front, *rear;
} LinkQueue;

/*!
 * 队列初始化
 * @param Q 队列
 */
void InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));
    Q.front->next = nullptr;
}

/*!
 * 判断队列是否为空
 * @param Q 队列
 * @return 如果队列为空返回true,否则返回false
 */
bool QueueEmpty(LinkQueue Q) {
    if (Q.front->next == nullptr)
        return true;
    else
        return false;
}

/*!
 *入队
 * @param Q 队列
 * @param x 入队元素
 * @return 入队成功返回true，否则返回false
 */
bool EnQueue(LinkQueue &Q, ElemType x) {
    auto q = (LinkNode *) malloc(sizeof(LinkNode));
    if (q == nullptr)
        return false;
    q->data = x;
    q->next = nullptr;
    Q.rear->next = q;
    Q.rear = q;
    return true;
}

/*!
 * 出队
 * @param Q 队列
 * @param x 存放出队元素的变量
 * @return 出队成功返回true，否则返回false
 */
bool DeQueue(LinkQueue &Q, ElemType &x) {
    if (QueueEmpty(Q))
        return false;
    LinkNode *q = Q.front->next;
    x = q->data;
    Q.front->next = q->next;
    if (Q.rear == q)
        Q.rear = Q.front;
    free(q);
    return true;
}

/*!
 * 获取对头元素
 * @param Q 队列
 * @param x 存放获取到的元素变量
 * @return 获取成功返回true，否则返回false
 */
bool GetHead(LinkQueue Q, ElemType &x) {
    if(QueueEmpty(Q))
        return false;
    x=Q.front->next->data;
    return true;
}